public class LC1071 {
    public String gcdOfStrings(String str1, String str2) {
        if (str1.isEmpty() || str2.isEmpty()) return "";
        String longestCommonSubStr = "";

        for (int i = 0; i < Math.min(str1.length(), str2.length()); i++) {
            int subStrLen = i + 1;
            if (str1.length() % subStrLen != 0 || str2.length() % subStrLen != 0) // 通过长度可以判断无法被整除
                continue;

            if (str1.charAt(i) != str2.charAt(i)) break; // 已经遍历所有可能的子串，可以提前终止
            String subStr = str1.substring(0, subStrLen);

            int nIters = str1.length() / subStrLen;
            boolean str1Flag = true;
            for (int j = 1; j < nIters; j++) {
                if (!str1.substring(j * subStrLen, (j + 1) * subStrLen).equals(subStr)) {
                    str1Flag = false;
                    break;
                }
            }
            if (!str1Flag) continue;

            nIters = str2.length() / subStrLen;
            boolean str2Flag = true;
            for (int j = 1; j < nIters; j++) {
                if (!str2.substring(j * subStrLen, (j + 1) * subStrLen).equals(subStr)) {
                    str2Flag = false;
                    break;
                }
            }

            if (str2Flag) longestCommonSubStr = subStr;
        }

        return longestCommonSubStr;
    }
}
